#define _CRT_SECURE_NO_WANINGS 1
#pragma warning(disable: 4996)
#include <stdio.h>
#include <string.h>
#include<stdlib.h>
typedef struct BinaryTree
{
    struct BinaryTree* left;
    struct BinaryTree* right;
    char c;
}tree;
tree* CreateNode(char s)
{
    tree* newnode = (tree*)malloc(sizeof(tree));
    newnode->c = s;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}
tree* TreeCreate(char* str, int* i)
{

    if (str[*i] == '#' || str[*i] == '\0')
    {
        return NULL;
    }
    tree* newnode = CreateNode(str[*i]);
    (*i)++;

    newnode->left = TreeCreate(str, i);
    (*i)++;
    newnode->right = TreeCreate(str, i);
    return newnode;

}
void prevoder(tree* head)
{
    if (head == NULL)
    {
        return;
    }

    prevoder(head->left);
    printf("%c ", head->c);
    prevoder(head->right);
}

int main() {
    char str[100] = { 0 };
    scanf("%s", str);
    int i = 0;
    tree* head = TreeCreate(str, &i);
    prevoder(head);
    return 0;
}
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool istwosame(struct TreeNode* root, struct TreeNode* subRoot)
{
    if (root == NULL && subRoot == NULL)
    {
        return true;
    }
    if ((root != NULL && subRoot == NULL) || (root == NULL && subRoot != NULL))
    {
        return false;
    }
    if (root->val != subRoot->val)
    {
        return false;
    }
    return istwosame(root->left, subRoot->left) && istwosame(root->right, subRoot->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if (root == NULL)
    {
        return false;
    }
    if (root->val == subRoot->val)
    {
        if (istwosame(root, subRoot))
        {
            return true;
        }
    }
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
struct TreeNode* invertTree(struct TreeNode* root) {
    if (root == NULL)
    {
        return NULL;
    }
    struct TreeNode* left = invertTree(root->left);
    struct TreeNode* right = invertTree(root->right);
    root->left = right;
    root->right = left;
    return root;
}